// https://www.lintcode.com/problem/decode-string/my-submissions

class Solution {
public:
    /**
     * @param s: an expression includes numbers, letters and brackets
     * @return: a string
     */
     
    // 法一：递归，TLE
    string expressionExpand(string s) {
        string res = "";
        int i = 0;
        while (i < s.length()) {
            int num = 0;
            if (s[i] >= '0' && s[i] <= '9') {
                while (s[i] >= '0' && s[i] <= '9') {
                    num = num * 10 + (s[i] - '0');
                    i++;
                }
            } 
            // else if (s[i] == '[') { i已经加上了
            if (s[i] == '[') {
                // int idx = s.find(']', i); 中间有括号的时候就错了
                // string tmp = expressionExpand(s.substr(i + 1, idx - i - 1));
                string tmp = "";
                int left = 1;
                int right = 0;
                int j = i + 1;
                for (; j < s.length(); ++j) {
                    if (s[j] == '[')
                        left++;
                    else if (s[j] == ']')
                        right++;
                    if (left == right) {
                        break;
                    }
                    tmp += s[j];
                }
                tmp = expressionExpand(tmp);
                for (int t = 0; t < num; ++t) {
                    res += tmp;
                }
                // i = idx + 1;
                i = j + 1;
            } else {
                res += s[i++];
            }
        }
        return res;
    }
    
    // 法二：栈
    // string expressionExpand(string s) {
    //     string res = "";
    //     stack<char> stack;
    //     for (int i = 0; i < s.length(); ++i) {
    //         string numStr = "";
    //         if (s[i] == ']') {
    //             string tmp = "";
    //             // while (stack.top() != '[') {
    //             while (!stack.empty() && stack.top() != '[') {
    //                 tmp += stack.top();
    //                 stack.pop();
    //             }
    //             reverse(tmp.begin(), tmp.end());
    //             stack.pop();
    //             // string numStr = "";
    //             // // while (stack.top() >= '0' && stack.top() <= '9') {
    //             // while (!stack.empty() && stack.top() >= '0' && stack.top() <= '9') { //注意！！！
    //             //     numStr += stack.top();
    //             //     stack.pop();
    //             // }
    //             // reverse(numStr.begin(), numStr.end());
    //             // int num = stoi(numStr);
    //             int num = 0;
    //             int base = 1;
    //             while (!stack.empty() && stack.top() >= '0' && stack.top() <= '9') {
    //                 // num = num * 10 + stack.top() - '0'; 反了
    //                 num += base * (stack.top() - '0');
    //                 base *= 10;
    //                 stack.pop();
    //             }
    //             for (int j = 0; j < num; ++j) {
    //                 for (char c: tmp) {
    //                     stack.push(c);
    //                 }
    //             }
    //         }
    //         else {
    //             stack.push(s[i]);
    //         }
    //     }
    //     while (!stack.empty()) {
    //         res += stack.top();
    //         stack.pop();
    //     }
    //     reverse(res.begin(), res.end());
    //     return res;
    // }
};